package com.coder.algorithm.offer_2;

import java.util.Arrays;
import java.util.Locale;

/**
 * 旋转数组的最小数字
 *
 * @author yuhushuan
 * @date 2020/6/7 23:42
 */
public class _11_1_MinNumberInRotatedArray {
    public static void main(String[] args) {
        System.out.println("旋转数组的最小数字\n");

        int[] array;

        // 功能测试（输入的数组是生序排序数组的一个旋转，数组中有重复数组或者没有重复数字）
        print(new int[]{4, 5, 6, 7, 8, 1, 2, 3});

        print(new int[]{2, 2, 2, 7, 8, 1, 2, 2});

        // 边界值测试（输入的数组是一个生序排序的数组，只包含一个数字的数组）
        print(new int[]{2});

        // 特殊输入测试（输入 null）
        // 边界值测试（输入的数组是一个生序排序的数组，只包含一个数字的数组）
        print(null);
    }

    private static void print(int[] array) {
        if (array == null) {
            try {
                System.out.println(String.format(Locale.getDefault(),
                        "旋转数组：\n%s\n最小数字为：%d"
                        , Arrays.toString(array), min(array)));
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }
        } else {
            System.out.println(String.format(Locale.getDefault(),
                    "旋转数组：\n%s\n最小数字为：%d"
                    , Arrays.toString(array), min(array)));
        }
        System.out.println();
    }

    private static int min(int[] array) throws IllegalArgumentException {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException("Invalid parameters array is null or array length is 0");
        }
        int left = 0;
        int right = array.length - 1;
        int mid = left;// 如果排序数组的前面的 0 个元素搬到后面
        while (array[left] >= array[right]) {
            if (right - left == 1) {
                mid = right;
                break;
            }
            mid = (left + right) >> 1;

            // 如果下标为 left、right 和 mid 指向的三个数字相等，则只能顺序查找
            if (array[left] == array[right] && array[mid] == array[left]) {
                return minInOrder(array, left, right);
            }

            if (array[mid] >= array[left]) {
                left = mid;
            } else if (array[mid] <= array[right]) {
                right = mid;
            }
        }
        return array[mid];
    }

    private static int minInOrder(int[] array, int left, int right) {
        int result = array[left];
        for (int i = left + 1; i <= right; i++) {
            if (result > array[i]) {
                result = array[i];
            }
        }
        return result;
    }
}
